

package java.util.concurrent.locks;

import sun.misc.Unsafe;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import java.util.concurrent.TimeUnit;

/**
 * 1、构建锁和同步器的框架
 * 2、CAS + CLH(虚拟的双向FIFO队列 )
 * 3、资源共享方式: Exclusive(独占)、Share(共享)
 * 4、AQS底层使用了模板方法模式
 * AQS 是实现 ReentrantLock、CountDownLatch、Semaphore、FutureTask 等类的基础。
 * 底层采用乐观锁，大量使用了CAS操作， 并且在冲突时，采用自旋方式重试，以实现轻量级和高效地获取锁
 */
public abstract class AbstractQueuedSynchronizer
        extends AbstractOwnableSynchronizer implements java.io.Serializable {


    /**
     * Java并发工具类的三板斧
     * <p>
     * 状态：一般是一个state属性，它基本是整个工具的核心，
     * 通常整个工具都是在设置和修改状态，很多方法的操作都依赖于当前状态是什么。
     * 由于状态是全局共享的，一般会被设置成volatile类型，以保证其修改的可见性；
     * <p>
     * 队列：队列通常是一个等待的集合，大多数以链表的形式实现。
     * 队列采用的是悲观锁的思想，表示当前所等待的资源，状态或者条件短时间内可能无法满足。
     * 因此，它会将当前线程包装成某种类型的数据结构，
     * 扔到一个等待队列中，当一定条件满足后，再从等待队列中取出。
     * <p>
     * CAS: CAS操作是最轻量的并发处理，通常我们对于状态的修改都会用到CAS操作，
     * 因为状态可能被多个线程同时修改，CAS操作保证了同一个时刻，
     * 只有一个线程能修改成功，从而保证了线程安全，CAS操作基本是由Unsafe工具类的compareAndSwapXXX来实现的；
     * CAS采用的是乐观锁的思想，因此常常伴随着自旋，如果发现当前无法成功地执行CAS，
     * 则不断重试，直到成功为止，自旋的的表现形式通常是一个死循环for(;;)。
     */
    private static final long serialVersionUID = 7373984972572414691L;

    /*
     * CAS是一条CPU的并发原语,其作用是判断内存某个位置的值是否为预期值,如果是则改为新的值,这个过程是原子的
     * Unsafe类中的CAS方法，JVM会帮我们实现出CAS汇编指令
     * 并且原语的执行必须是连续的，在执行过程中不予许被中断，也就是说CAS是一条CPU的原语指令，不会造成所谓的数据不一致问题。
     * CAS的缺点
     *  1、循环时间长，开销大。如果CAS失败，会一直进行尝试，如果CAS长时间一直不成功，可能会给CPU带来很大的开销
     *  2、只能保证一个共享变量的原子操作
     *  3、会导致ABA问题
     */

    /*
     * 锁的状态
     * state <= 0 表示锁没有被占用
     * state > 0  表示当前已经有线程持有该锁,或者已经重入
     */
    private volatile int state;            //共享变量,使用volatile修饰保证线程可见行
    // 头节点
    private transient volatile Node head;
    // 尾节点
    private transient volatile Node tail;
    // Unsafe类实例
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    // state内存偏移地址
    private static final long stateOffset;
    // head内存偏移地址
    private static final long headOffset;
    // tail内存偏移地址
    private static final long tailOffset;
    // waitStatus内存偏移地址
    private static final long waitStatusOffset;
    // next内存偏移地址
    private static final long nextOffset;

    static {
        try {
            // 初始化偏移量,通过使用objectFieldOffset方法
            // 参数Field,获取对应字段的偏移量
            stateOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    //构造函数
    protected AbstractQueuedSynchronizer() {
    }

    //返回同步状态的当前值
    protected final int getState() {
        return state;
    }

    //设置同步状态值
    protected final void setState(int newState) {
        state = newState;
    }


    //------------------------------------------------------------------------------------------------
    // 五大 AQS模版方法

    /**
     * AQS模版方法，自定义同步器需要重写
     * 1、默认情况下，每个方法都抛出 UnsupportedOperationException
     * 2、这些方法的实现必须是内部线程安全的，并且通常应该简短而不是阻塞
     * 3、AQS类中的其他方法都是final ，所以无法被其他类使用，只有这几个方法可以被其他类使用
     */

    //独占方式。尝试获取资源，成功则返回true，失败则返回fals
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    //独占方式。尝试释放资源，成功则返回true，失败则返回false
    // 三种锁释放
    // 1、ReentrantLock
    // 2、ReentrantReadWriteLock
    // 3、Worker
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    //共享方式。尝试获取资源。负数表示失败；0表示成功，但没有剩余可用资源；正数表示成功，且有剩余资源
    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }

    //共享方式。尝试释放资源，成功则返回true，失败则返回false
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    //该线程是否正在独占资源。只有用到condition才需要去实现它
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    //------------------------------------------------------------------------------------------------
    // 五大 CAS线程安全操作

    /**
     * CAS操作设置头节点
     * 该方法用于原子地将头节点设置为给定的节点
     * 主要在实现同步机制时使用，以确保线程安全
     *
     * @param update 要设置为新头节点的节点
     * @return 如果设置成功则返回true，否则返回false
     */
    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    /**
     * CAS操作设置尾节点
     * 该方法用于原子地将尾节点从预期节点设置为给定的节点
     * 主要在实现同步机制时使用，以确保线程安全
     *
     * @param expect 当前预期的尾节点
     * @param update 要设置为新尾节点的节点
     * @return 如果设置成功则返回true，否则返回false
     */
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    /**
     * CAS操作设置节点的等待状态
     * 该方法用于原子地将节点的等待状态从预期状态设置为给定的状态
     * 主要在实现同步机制时使用，以确保线程安全
     *
     * @param node   要更新的节点
     * @param expect 当前预期的等待状态
     * @param update 要设置的新等待状态
     * @return 如果设置成功则返回true，否则返回false
     */
    private static final boolean compareAndSetWaitStatus(Node node, int expect, int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset, expect, update);
    }

    /**
     * CAS操作设置节点的下一个节点
     * 该方法用于原子地将节点的下一个节点从预期节点设置为给定的节点
     * 主要在实现同步机制时使用，以确保线程安全
     *
     * @param node   要更新的节点
     * @param expect 当前预期的下一个节点
     * @param update 要设置为新下一个节点的节点
     * @return 如果设置成功则返回true，否则返回false
     */
    private static final boolean compareAndSetNext(Node node, Node expect, Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }

    /**
     * 使用CAS（Compare And Swap）操作来设置状态
     * 此方法用于原子性地更新状态，如果当前状态与预期值匹配，则设置为新的状态
     *
     * @param expect 预期的当前状态值
     * @param update 新的状态值
     * @return 如果更新成功则返回true，否则返回false
     */
    protected final boolean compareAndSetState(int expect, int update) {
        // 使用Unsafe类的compareAndSwapInt方法实现CAS操作
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    //------------------------------------------------------------------------------------------------
    // 独占锁模式


    /**
     * 独占锁模式，忽略中断。
     * 通过至少调用一次tryAcquire来实现，成功后返回。
     * 否则，线程将排队，可能会重复阻塞和取消阻塞，调用tryAcquire直到成功。此方法可用于实现方法Lock.Lock。
     */
    public final void acquire(int arg) {
        // 尝试获取锁,中断此线程是无效的
        if (!tryAcquire(arg) &&
                // 线程没有获取锁失败情况下,自旋等待队列
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            // 没有上锁成功 && 加入等待队列失败, 线程中断
            selfInterrupt();
    }

    /**
     * 独占锁模式获取,如果线程中断则中止
     * 首先检查线程中断状态,然后至少调用一次tryAcquire,在成功时返回来实现，
     * 否则,线程将排队,可能会重复阻塞和取消阻塞,调用tryAcquire直到成功或线程中断
     */
    public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        // 检查线程中断状态
        if (Thread.interrupted())
            throw new InterruptedException();

        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
    }

    private void doAcquireInterruptibly(int arg) //整段代码和acquireQueued差不多的，唯一的区别在异常
            throws InterruptedException {
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }

                // 看这里,如果parkAndCheckInterrupt返回true,表示线程唤醒前曾被调用Interrupt()
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    /**
     * 尝试以独占锁模式进行获取，如果中断则中止，如果超过给定超时则失败。
     * 通过首先检查中断状态，然后至少调用一次tryAcquire，在成功时返回来实现。否则，线程将排队，可能会重复阻塞和取消阻塞，
     * 调用tryAcquire，直到成功或线程中断或超时。此方法可用于实现方法Lock.tryLock（long，TimeUnit）。
     */
    public final boolean tryAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquire(arg) ||
                doAcquireNanos(arg, nanosTimeout);
    }


    /**
     * 独占模式获取,并设置超时时间
     */
    private boolean doAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        // 如果nanosTimeout小于0直接返回
        if (nanosTimeout <= 0L)
            return false;

        // 通过将当前时间 + 设置的超时时间 = 超时时间点
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;

        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                // 超时时间点 - 当前时间 = 剩余的超时时间
                nanosTimeout = deadline - System.nanoTime();
                // 如果剩余时间小于0说明已经超时,则返回
                if (nanosTimeout <= 0L)
                    return false;
                // 如果没有超时则等待nanosTimeout
                // 注意:该线程会直接从LockSupport.parkNanos(this, nanosTimeout)中返回
                // LockSupport是JUC提供的一个阻塞和唤醒的工具类
                if (shouldParkAfterFailedAcquire(p, node) &&
                        //如果nanosTimeout大于spinForTimeoutThreshold，就需要休眠nanosTimeout
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);

                //如果nanosTimeout小于等于spinForTimeoutThreshold，那么就不需要休眠了，直接进入快速自旋
                // 因为spinForTimeoutThreshold已经很短了，如果在更短的超时时间内还要休眠，可能会导致超时时间不那么准确
                //线程的状态切换是需要时间的
                // 判断线程是否已经中断了
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    /**
     * 独占模式下释放锁，主要是调用 tryRelease
     * 1、首先就是考虑之前的重入问题，直接对 state 进行 -1
     * 2、然后如果 c == 0表示当前线程不再持有锁，我们就可以修改 ownerThread == null
     * 3、这个时候，最后修改 state 为新值。
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            // 如果头结点不为空，并且头结点的状态值不为0，则唤醒头结点
            if (h != null && h.waitStatus != 0)
                // 成功释放锁后,唤醒排队线程(排队的线程为头结点)
                unparkSuccessor(h); //release
            return true;
        }
        return false;
    }

    /**
     * 唤醒等待队列中的后继节点,当一个节点被释放，该方法尝试唤醒在等待队列中的后继节点
     * 1、独占模式下解锁后,唤醒
     * 2、共享模式下解锁后,唤醒
     * 3、取消锁定后，唤醒
     * @param node 刚刚被释放的节点
     */
    private void unparkSuccessor(Node node) {
        // 获取节点的状态，如果状态小于0，表示节点曾经被取消过
        int ws = node.waitStatus;
        if (ws < 0)
            // 将节点的状态设置为0，表示节点已经不再需要被取消
            compareAndSetWaitStatus(node, ws, 0);

        // 获取当前节点的后继节点
        Node s = node.next;
        // 如果后继节点为空或者状态大于0（表示后继节点已经被取消），则需要找到一个合适的节点来唤醒
        if (s == null || s.waitStatus > 0) {
            s = null;
            // 从尾部开始向前遍历，找到一个状态不大于0的节点，作为新的后继节点
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        // 如果找到了合适的后继节点，则唤醒该节点对应的线程
        if (s != null)
            LockSupport.unpark(s.thread);
    }

    //------------------------------------------------------------------------------------------------
    // 共享锁模式

    /**
     * 共享模式下加锁
     * <p> 1、读锁支持重入的共享锁
     * <p> 2、同一时刻它能被多个线程同时获取,在没有其他写线程访问时,读锁总会被获取成功
     * <p> 3、如果当前线程已经获取读锁,则增加读状态
     * <p> 4、如果当前线程再获取读锁时，写锁已经被其他线程获取,则进入等待状态
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

    /**
     * 以共享方式获取
     * 如果中断，中止。 首先检查中断状态，然后调用至少一次tryAcquireShared(int) ，成功返回。
     * 否则线程排队，可能会重复阻塞和解除阻塞，调用tryAcquireShared(int)直到成功或线程中断。
     *
     * @param arg 获取的论据。 该值传达给tryAcquireShared(int) ，否则无法解释，可以代表您喜欢的任何内容。
     * @throws InterruptedException 当前线程是否中断
     */
    public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        // 判断当前线程是否中断
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0) {
            doAcquireSharedInterruptibly(arg);
        }
    }

    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquireShared(arg) >= 0 ||
                doAcquireSharedNanos(arg, nanosTimeout);
    }

    /**
     * 共享模式下释放锁，主要是调用 tryReleaseShared
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    //------------------------------------------------------------------------------------------------
    // 操作CLH队列

    /**
     * 独占锁和共享锁都可以调用的入队方法，添加等待者
     * 入列,说明前面获取锁失败,放在队列中等待
     */
    private Node addWaiter(Node mode) {
        //当前线程以某种模式(共享或独占)添加到AQS Node结点(CLH队列)
        Node node = new Node(Thread.currentThread(), mode);
        // 获取AQS中队列的尾部节点
        Node pred = tail;

        if (pred != null) {
            // 尾结点不为空，即已经被初始化
            // 当前节点的前驱节点指向尾节点
            node.prev = pred;
            // cas 修改 tail 节点，如果成功返回 node
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }

        // enq方法会使用无限循环来确保节点的成功插入。
        // 进入该方法的场景:
        // 1、没人排队,我是第一个进入队列的对象
        // 2、前面CAS失败,会跳到enq方法,进行CAS频繁循环竞争队尾
        enq(node);    //addWaiter
        return node;
    }


    /**
     * CAS 自旋竞争队尾
     * 将节点插入队列，必要时进行初始化。
     */
    private Node enq(final Node node) {
        //无限循环，确保结点能够成功入队列
        for (; ; ) {
            // 重新获取当前的tail节点
            Node t = tail;
            if (t == null) {
                // 尾结点为空，即还没被初始化
                // 头节点为空，并设置头节点为新生成的结点
                if (compareAndSetHead(new Node()))
                    tail = head;
            }
            // 有人排队,在队列尾巴塞
            else {
                node.prev = t;
                //将node结点的prev域连接到尾结点
                //比较结点t是否为尾结点，若是则将尾结点设置为node
                //设置尾结点的next域为node
                //返回尾结点
                if (compareAndSetTail(t, node)) {
                    t.next = node;
                    return t;
                }
            }
        }
    }


    /**
     * sync队列(CLH队列)中的结点在独占且忽略中断的模式下获取(资源)
     */
    final boolean acquireQueued(final Node node, int arg) {
        //标志
        boolean failed = true;
        try {
            // 中断标志
            boolean interrupted = false;
            // 自旋
            for (; ; ) {
                // 获取node的前驱节点
                final Node p = node.predecessor();
                // 如果node结点 == CLH队列的第一个结点逻辑
                if (p == head && tryAcquire(arg)) {
                    // 如果是头节点，再次尝试获取锁
                    // 为什么用 p==head 判断是头结点呢？
                    // 1、CLH队列为空的时候，添加node结点后,prev就是头节点(头节点就是空对象，head.prev==null,head.next==node)
                    // 2、因为第一次添加队列的时候，tail和head的指向的Node结点地址值一样
                    setHead(node);   //设置头节点
                    p.next = null;   //help GC
                    failed = false;  //设置标志
                    return interrupted;
                }
                // 如果node结点
                // 判断是否需要进行阻塞当前线程
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())  // 阻塞线程
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 最终方法，判断当前线程是否有排队的前驱节点
     * 此方法用于同步队列中，确定当前线程是否是第一个等待资源的线程
     * @return 如果当前线程有排队的前驱节点，则返回true；否则返回false
     */
    public final boolean hasQueuedPredecessors() {
        // 获取队列的尾节点
        Node t = tail;
        // 获取队列的头节点
        Node h = head;
        // 用于存储头节点的下一个节点
        Node s;
        // 第二种情况: 队列中有多个元素，且头节点的下一个节点为空或不是当前线程，此时当前线程有排队的前驱节点
        return
                // h==t ---> return false
                // h==t会有两种情况
                //  1、空队列, h==t==null
                //  2、队列只有一个Node结点,因为只有一个Node的时候, h==t,head和tail指向同一个Node对象
                h != t
                        // 代码走到这里,说明CLH队列存在至少一个Node结点在等待
                        // 此步骤会有两个逻辑判断
                        // h.next==null --> 队列中只有一个Node结点等待
                        // h.next.thread != Thread.currentThread() --> 等待的结点并不是当前线程
                        && ((s = h.next) == null || s.thread != Thread.currentThread());
    }

    /**
     * 当获取锁失败后, 检查更新新节点状态如果是需要阻塞返回, true
     * 一个前继节点 waitStatus = 0,
     * 第一次将继续设置为 SIGNAL, 告诉当前线程准备进入阻塞, 此时依旧获取不到, 当前线程进入阻塞
     * @param pred 前继节点
     * @param node 当前节点
     * @return {@code true} if thread should block
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        // 前继节点的状态, 第一次进入的话, 一定是 0
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL) return true;

        if (ws > 0) {
            // 出队, 剔除无效的节点
            do {
                //代码执行过程
                //pred.prev 获取当前节点的前驱节点的前驱节点。
                //pred = pred.prev 将 pred 更新为当前节点的前驱节点的前驱节点。
                //node.prev = pred 将当前节点的前驱节点更新为新的 pred。
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);

            pred.next = node;
        } else {
            // 第一次进来, pred.waitStatus = 0 执行这个分支
            // 将前继节点的状态修改为 SIGNAL, 表示 pred.next 节点需要被唤醒(此时准备进入阻塞, 但是还未被阻塞, 再次获取锁失败之后才会被阻塞)
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }


    //---------------------------------------------------------------------------------------------
    // 内部类 Node、ConditionObject

    /**
     * CLH同步队列,双向链表
     * 主要用于实现自旋锁,特别是在多处理器系统中。
     */
    static final class Node {

        // 共享模式
        static final Node SHARED = new Node();
        // 独占模式 (排他锁标识)
        static final Node EXCLUSIVE = null;

        // 结点状态
        // CANCELLED，值为1，表示当前的线程被取消
        // SIGNAL，值为-1，表示当前节点的后继节点包含的线程需要运行，也就是unpark
        // CONDITION，值为-2，表示当前节点在等待condition，也就是在condition队列中
        // PROPAGATE，值为-3，表示当前场景下后续的acquireShared能够得以执行
        // 值为0，表示当前节点在sync队列中，等待着获取锁
        static final int CANCELLED = 1;
        static final int SIGNAL = -1;
        static final int CONDITION = -2;
        static final int PROPAGATE = -3;

        // 节点状态,标记当前节点的信号量状态 (1,0,-1,-2,-3)5种状态
        volatile int waitStatus; //使用CAS更改状态，volatile保证线程可见性，高并发场景下，即被一个线程修改后，状态会立马让其他线程可见
        // 前驱结点
        volatile Node prev;
        // 后驱结点
        volatile Node next;
        // 结点所对应的线程
        volatile Thread thread;
        // 条件队列(单向列表)
        // nextWaiter是没用volatile修饰的,因为线程在调用await方法进入条件队列时，是已经拥有了锁的，此时是不存在竞争的情况，
        // 所以无需通过volatile和cas来保证线程安全。而进入同步队列的都是抢锁失败的，所以肯定是没有锁的，故要考虑线程安全
        // 最后需要注意一点的是，条件队列里面的Node只会存在CANCELLED和CONDITION的状态
        Node nextWaiter;

        Node() {
        }

        Node(Thread thread, Node mode) {
            this.nextWaiter = mode;
            this.thread = thread;
        }

        Node(Thread thread, int waitStatus) {
            this.waitStatus = waitStatus;
            this.thread = thread;
        }

        // 结点是否在共享模式下等待
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        // 获取前驱结点，若前驱结点为空，抛出异常
        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }
    }

    /**
     * ConditionObject内部通过链表来维护等待队列（条件队列）
     * 1、Contidion必须在lock的同步控制块中使用，调用Condition的signal方法并不代表线程可以马上执行
     * 2、signal方法的作用是将线程所在的节点从等待队列中移除，然后加入到同步队列中，线程的执行始终都需要根据同步状态（即线程是否占有锁）
     * <p> 每个条件变量都维护了一个容器，ConditionObject中的容器就是单向链表队列
     * <p> 条件队列中的头结点不是虚拟头结点，而是包装了等待线程的节点！
     * <p> 条件队列是一个单向链表，所以他并没有使用Node类中的next属性来关联后继Node，而使用的nextWaiter
     */
    public class ConditionObject implements Condition, java.io.Serializable {
        private static final long serialVersionUID = 1173984872572414699L;
        // 队列头节点
        private transient Node firstWaiter;
        // 队列尾节点
        private transient Node lastWaiter;


        public ConditionObject() {
        }

        // Internal methods

        // 添加一个等待Node到条件队列中
        private Node addConditionWaiter() {
            Node t = lastWaiter;
            // 如果最后一个等待节点的状态不是 CONDITION，说明已经被取消了，进行清理
            if (t != null && t.waitStatus != Node.CONDITION) {
                unlinkCancelledWaiters(); // 清理条件队列中的不是CONDITION 类型的节点
                t = lastWaiter;
            }

            //新建一个Condition状态的节点,并将其加在尾部
            Node node = new Node(Thread.currentThread(), Node.CONDITION);

            // 校验队列位置
            if (t == null)
                // 尾结点为空,只有头节点的时候nextWaiter为null
                // 设置condition队列的头节点
                firstWaiter = node;
            else
                // 尾结点不为空
                // 设置为节点的nextWaiter域为node结点
                t.nextWaiter = node;

            // 更新condition队列的尾结点
            lastWaiter = node;
            return node;
        }


        // signal则只转移条件队列中的第一个状态不为CANNCELLED的Node
        private void doSignal(Node first) {
            // 循环
            do {
                // 将firstWaiter指向传入的first的后继节点，为null说明条件队列中只有first这一个节点,将整个队列清空
                if ((firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                first.nextWaiter = null;
                // transferForSignal如果返回为false，说明节点进入同步队列失败（已经被取消了）
                // 判断此节点的下一个节点是否为null，如果不为null，则会再次进入循环将这个节点进行入队
            } while (!transferForSignal(first) && (first = firstWaiter) != null);
        }

        /**
         * 将条件队列中的所有 Node 移动到同步队列中
         */
        private void doSignalAll(Node first) {
            // 唤醒有等待此condition的所有线程条件
            // first为队首,所以单向列表就能拿到所有数据
            // 可以把lastWaiter/firstWaiter 设置成null了
            lastWaiter = firstWaiter = null;

            // 通过循环将条件队列中每个node移动到同步队列
            do {
                Node next = first.nextWaiter;
                first.nextWaiter = null; // help GC
                // 将此node转移到同步队列中
                transferForSignal(first);
                first = next;
            } while (first != null);
        }

        // 从Condition队列中清除状态为CANCEL的结点，比如中断、超时等会导致节点转换为Cancel
        private void unlinkCancelledWaiters() {
            Node t = firstWaiter;
            Node trail = null;

            while (t != null) {  // t不为空
                Node next = t.nextWaiter; // 下一个结点
                if (t.waitStatus != Node.CONDITION) { // t结点的状态不为CONDTION状态
                    t.nextWaiter = null;              // 设置t节点的nextWaiter域为空
                    if (trail == null)
                        // trail为空
                        // 重新设置condition队列的头节点
                        firstWaiter = next;
                    else
                        // trail不为空
                        // 设置trail结点的nextWaiter域为next结点
                        trail.nextWaiter = next;
                    if (next == null)
                        // next结点为空
                        // 设置condition队列的尾结点
                        lastWaiter = trail;
                } else
                    // t结点的状态为CONDTION状态
                    // trail 指向的是正常节点
                    trail = t;
                // 设置t结点
                t = next;
            }
        }


        // public methods

        //signal则只转移条件队列中的第一个状态不为CANNCELLED的Node
        public final void signal() {
            // 查看此时线程是否已经获取了锁
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            // 转移条件队列中的第一个状态不为CANNCELLED的Node
            if (first != null)
                doSignal(first);
        }

        /**
         * 将条件队列中的所有Node移到同步队列中，然后根据条件再唤醒它们去尝试获得锁
         */
        public final void signalAll() {
            // 查看此时线程是否已经获取了锁
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();

            // 将条件队列中所有Node移动到同步队列中
            Node first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }

        public final void awaitUninterruptibly() {
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean interrupted = false;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if (Thread.interrupted())
                    interrupted = true;
            }
            if (acquireQueued(node, savedState) || interrupted)
                selfInterrupt();
        }

        // await方法退出时，会重新再中断一次
        private static final int REINTERRUPT = 1;
        // await方法退出时，会抛出InterruptedException异常
        private static final int THROW_IE = -1;

        /**
         * 检查等待的时间内是否被中断过
         * <p> 没有中断则返回0
         * <p> 发生中断，我们需要通过transferAfterCancelledWait方法进一步检查其他线程是否执行了唤醒操作
         * <p> 中断先于其他线程调用signal等方法唤醒的，返回THROW_IE，await方法退出时，会抛出InterruptedException异常
         * <p> 中断是后于其他线程调用signal等方法唤醒，返回REINTERRUPT，await方法退出时，会重新再中断一次
         */
        private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                    (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                    0;
        }


        private void reportInterruptAfterWait(int interruptMode)
                throws InterruptedException {
            if (interruptMode == THROW_IE)
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT)
                selfInterrupt();
        }


        /**
         * 实现可中断条件等待。
         * 1、如果当前线程被中断，则抛出InterruptedException。
         * 2、保存getState返回的锁定状态。
         * 3、以保存的状态为参数调用发布，如果失败，则抛出IllegalMonitorStateException。
         * 4、阻塞，直到发出信号或中断。
         * 5、通过调用以保存状态为参数的专门版本的获取来重新获取。
         * 6、如果在步骤4中被阻止时被中断，则抛出InterruptedException。
         */
        public final void await() throws InterruptedException {
            // 如果当前线程被中断,抛出异常
            if (Thread.interrupted())
                throw new InterruptedException();
            // 将调用 await 的线程包装成 Node, 添加到添加队列并返回
            Node node = addConditionWaiter();
            // 完全释放节点持有的锁,因为其他线程唤醒当前线程的前提是[持有锁]
            int savedState = fullyRelease(node);
            // 设置打断模式为没有被打断
            int interruptMode = 0;
            // 如果不在同步队列中
            while (!isOnSyncQueue(node)) {
                // 此线程就被 park 方法阻塞了，只有当线程被唤醒才会在这里开始继续执行下面代码
                LockSupport.park(this);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null) // clean up if cancelled
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }


        public final long awaitNanos(long nanosTimeout)
                throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }


        public final boolean awaitUntil(Date deadline)
                throws InterruptedException {
            long abstime = deadline.getTime();
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (System.currentTimeMillis() > abstime) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                LockSupport.parkUntil(this, abstime);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }


        /*
         * 等待，当前线程在接到信号、被中断或到达指定等待时间之前一直处于等待状态。
         * 此方法在行为上等效于: awaitNanos(unit.toNanos(time)) > 0
         * @throws InterruptedException
         */
        public final boolean await(long time, TimeUnit unit)
                throws InterruptedException {
            long nanosTimeout = unit.toNanos(time);
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();    //只有线程持有锁的情况下,才能添加到Condition队列中
            int savedState = fullyRelease(node); //将当前线程持有的锁释放掉
            final long deadline = System.nanoTime() + nanosTimeout;
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }


        //  support for instrumentation


        final boolean isOwnedBy(AbstractQueuedSynchronizer sync) {
            return sync == AbstractQueuedSynchronizer.this;
        }

        protected final boolean hasWaiters() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    return true;
            }
            return false;
        }

        protected final int getWaitQueueLength() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            int n = 0;
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    ++n;
            }
            return n;
        }

        protected final Collection<Thread> getWaitingThreads() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            ArrayList<Thread> list = new ArrayList<Thread>();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION) {
                    Thread t = w.thread;
                    if (t != null)
                        list.add(t);
                }
            }
            return list;
        }
    }


    // Queuing utilities

    static final long spinForTimeoutThreshold = 1000L;


    /**
     * 将队列的头设置为node节点，从而出列。
     * 仅由获取方法调用
     * 为了GC和抑制不必要的信号和遍历，还将未使用的字段置零。
     */
    private void setHead(Node node) {
        head = node;
        node.thread = null;
        node.prev = null;
    }





    /**
     * 释放共享资源的方法
     * 该方法用于在释放共享资源时，唤醒等待队列中的后继节点
     * 在高并发环境下，通过循环和CAS操作来确保线程安全
     */
    private void doReleaseShared() {
        for (; ; ) {
            Node h = head;
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    unparkSuccessor(h); //doReleaseShared
                } else if (ws == 0 &&
                        !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            if (h == head)                   // loop if head changed
                break;
        }
    }


    private void setHeadAndPropagate(Node node, int propagate) {
        Node h = head; // Record old head for check below
        setHead(node);
        if (propagate > 0 || h == null || h.waitStatus < 0 ||
                (h = head) == null || h.waitStatus < 0) {
            Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }


    /**
     * 取消节点
     */
    private void cancelAcquire(Node node) {
        // Ignore if node doesn't exist
        if (node == null)
            return;

        // 当前节点的线程指向置为null
        node.thread = null;

        // 协同取消的处理
        // 这里是判断当前节点的上一个节点状态是否是取消状态(状态大于0只有是取消状态)
        // 如果上一个节点是取消状态,那么继续向上遍历,直到找到状态为小于0的状态节点
        // 并且把当前节点的prev指向非取消节点。
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        // 得到没有取消节点的下一个节点
        Node predNext = pred.next;

        // 因为当前cancelAcquire()方法就是取消处理
        // 所以将当前节点设置成取消状态
        node.waitStatus = Node.CANCELLED;

        // 如果当前取消的节点是tail节点，也就是最后一个节点
        // 那么就把tail指针指向上面while循环遍历出的prev节点(因为要指向一个没有被取消的节点)
        if (node == tail && compareAndSetTail(node, pred)) {
            // help GC
            // 为什么说help GC呢？
            // 因为把prev的next节点设置为null，
            // 这样GC ROOT扫描发现没有根节点的引用。
            compareAndSetNext(pred, predNext, null);
        } else {
            // 走到else代表当前节点不是tail节点，或者是cas操作的时候tail发生了变化
            // 如果不是tail节点，不能直接把tail节点指向到上面while循环得出的prev节点
            int ws;
            // 这里是的if代码块，是为了尝试一次，如果不成功再去复杂的处理。
            // 这里的if判断条件如下：
            // 1.如果上面while循环得到的prev节点不是head节点
            // 2.如果上面while循环得到的prev节点为-1，如果不为-1，cas改变成-1也。
            // 3.如果上面while循环得到的rpev节点的线程指向不为null(如果为null代表在取消的过程中)
            // 因为&&是拼接，所以上面任意一个条件为false就会进入到else条件中。
            if (pred != head &&
                    ((ws = pred.waitStatus) == Node.SIGNAL ||
                            (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                    pred.thread != null) {
                // 进到这里代表这次尝试成功了。
                // 得到当前节点的下一个节点
                // 然后把前面while循环得到的prev节点的next指向当前节点的next节点。
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    compareAndSetNext(pred, predNext, next);
            } else {
                // 直接唤醒当前节点的下一个节点。
                // 唤醒的目的是为了去执行shouldParkAfterFailedAcquire方法去处理取消节点。
                unparkSuccessor(node); //cancelAcquire
            }
            // 把当前节点的下一个节点指向自己.
            node.next = node; // help GC
        }
    }




    /**
     * 用于当前线程自我中断的方法
     * 此方法旨在提供一个集中点，以便线程可以中断自身
     * 它封装了中断当前线程的操作，使得在代码的其他部分需要中断线程时，可以调用此方法
     * 这样做提高了代码的可读性和可维护性，同时确保了中断操作的一致性
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }


    /**
     * 阻塞当前线程，并检查线程是否被中断
     * 使用LockSupport.park方法阻塞当前线程，该方法会一直阻塞线程直到线程被中断或取消阻塞
     * 然后，通过Thread.interrupted方法返回线程的中断状态，并清除中断状态
     *
     * @return boolean 返回线程的中断状态如果线程已被中断，则返回true；否则返回false
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this); //阻塞线程
        return Thread.interrupted();    //返回线程中断状态
    }


    private void doAcquireShared(int arg) {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    private void doAcquireSharedInterruptibly(int arg)
            throws InterruptedException {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return true;
                    }
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }


    // Queue inspection methods

    /**
     * 查询是否有线程正在等待获取
     */
    public final boolean hasQueuedThreads() {
        return head != tail;
    }

    public final boolean hasContended() {
        return head != null;
    }

    public final Thread getFirstQueuedThread() {
        return (head == tail) ? null : fullGetFirstQueuedThread();
    }

    private Thread fullGetFirstQueuedThread() {
        Node h, s;
        Thread st;
        if (((h = head) != null && (s = h.next) != null &&
                s.prev == head && (st = s.thread) != null) ||
                ((h = head) != null && (s = h.next) != null &&
                        s.prev == head && (st = s.thread) != null))
            return st;

        Node t = tail;
        Thread firstThread = null;
        while (t != null && t != head) {
            Thread tt = t.thread;
            if (tt != null)
                firstThread = tt;
            t = t.prev;
        }
        return firstThread;
    }


    public final boolean isQueued(Thread thread) {
        if (thread == null)
            throw new NullPointerException();
        for (Node p = tail; p != null; p = p.prev)
            if (p.thread == thread)
                return true;
        return false;
    }

    final boolean apparentlyFirstQueuedIsExclusive() {
        Node h, s;
        return (h = head) != null &&
                (s = h.next) != null &&
                !s.isShared() &&
                s.thread != null;
    }





    // Instrumentation and monitoring methods

    /**
     * 获取队列长度
     * 此方法用于统计队列中有效节点的数量有效节点是指其thread字段不为空的节点
     * 方法从队列的尾部开始遍历，直到头部，累加有效节点的数量
     *
     * @return 队列中有效节点的数量
     */
    public final int getQueueLength() {
        // 初始化计数器为0，用于统计有效节点的数量
        int n = 0;
        // 从队列的尾部开始遍历，直到头部
        for (Node p = tail; p != null; p = p.prev) {
            // 如果当前节点的thread字段不为空，则认为这是一个有效节点，并累加计数
            if (p.thread != null)
                ++n;
        }
        // 返回有效节点的数量
        return n;
    }

    /**
     * 获取当前正在排队等待的线程集合
     * 此方法用于返回所有正在排队等待进入此锁的线程集合通过遍历内部维护的线程等待队列来收集这些线程
     * 注意，这个方法提供了一个快照视图，因此，在返回线程集合后，实际的等待线程情况可能已经发生变化
     *
     * @return Collection<Thread> 返回当前正在排队等待的线程集合
     */
    public final Collection<Thread> getQueuedThreads() {
        // 创建一个ArrayList来存储排队等待的线程
        ArrayList<Thread> list = new ArrayList<Thread>();
        // 从队列的尾部开始向前遍历，收集所有非空的线程
        for (Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            // 如果当前节点的线程不为空，则将其添加到列表中
            if (t != null)
                list.add(t);
        }
        // 返回收集到的线程列表
        return list;
    }


    public final Collection<Thread> getExclusiveQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }

    public final Collection<Thread> getSharedQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }


    public String toString() {
        int s = getState();
        String q = hasQueuedThreads() ? "non" : "";
        return super.toString() +
                "[State = " + s + ", " + q + "empty queue]";
    }


    // Internal support methods for Conditions

    /**
     * 判断节点是否在AQS同步队列中
     */
    final boolean isOnSyncQueue(Node node) {
        // node 的状态是 CONDITION，或者前驱节点为空，说明此节点是在条件队列中
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        // 说明当前节点已经成功入队到同步队列，且当前节点后面已经有其它 node
        if (node.next != null)
            return true;

        // 说明【可能在同步队列，但是是尾节点】
        // 从同步队列的尾节点开始向前【遍历查找 node】，如果查找到返回 true，查找不到返回 false
        return findNodeFromTail(node);
    }

    /**
     * 从同步队列的尾节点，向前遍历查找node
     */
    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for (; ; ) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

    /**
     * 将node转移到同步队列中
     */
    final boolean transferForSignal(Node node) {

        // 说明此节点状态为CANCELLED，所以跳过该节点（GC会回收）
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;

        // 将 node 加入到队尾, enq 返回的是node的前驱节点
        Node p = enq(node); //transferForSignal
        int ws = p.waitStatus;

        // 1、前驱节点状态是CANCELLED
        // 2、前驱节点不是CANCELLED状态，但CAS将状态变为SIGNAL失败
        //    此时会唤醒线程，去尝试获取锁，此时会来到await()方法中的acquireQueued()方法,
        //    acquireQueued()方法中的shouldParkAfterFailedAcquire()方法会
        //    往前找，直到找到最近一个正常等待的状态，将该节点排在它的后边
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }

    /**
     * 如有必要，在取消等待后将节点转移至同步队列。若线程在收到信号前被取消，则返回真。
     */
    final boolean transferAfterCancelledWait(Node node) {
        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            enq(node); //transferAfterCancelledWait
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;
    }

    /**
     * 将当前线程持有的锁释放掉
     */
    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            int savedState = getState();  //返回锁状态
            if (release(savedState)) {    //释放锁
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            // 没有释放成功，将当前 node 设置为取消状态
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

    // Instrumentation methods for conditions

    public final boolean owns(ConditionObject condition) {
        return condition.isOwnedBy(this);
    }

    public final boolean hasWaiters(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
    }

    public final int getWaitQueueLength(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
    }

    public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
    }


}
